
public class Dijkstra 
{
	private GrafOrientat graf;
	private int [] p , d;
	private int  inf = 999999999;

	public Dijkstra(GrafOrientat graf) 
	{
		this.graf = graf;
	}
	
	private void alg()
	{
		int n = graf.getNrVarfuri() , nvizitat = n-1;
		boolean [] viz = new boolean[n];
		p = new int[n];
		d = new int[n];
		
		for(int i=1;i<n;i++)
			d[i] = inf;
		
		while(nvizitat > 0)
		{
			Muchie [] e = new Muchie[graf.getNIncidenta()];
			e = graf.getListaInc();
			int x = inf;
			for(int i=0;i<n;i++)
				if(d[i] < x && viz[i] == false)
					x = i;
			viz[x] = true;
			nvizitat--;
			
			int m = graf.getNIncidenta(); 
			System.out.println("m="+m);
			for(int i=0;i<m;i++)
				if(e[i].from == x)
					{
						int y = e[i].to;
						if(d[x] + e[i].val < d[y])
							{
								d[y] = e[i].val + d[x];
								p[y] = x;
							}	
					}
		}
	}
		
		
		public String getDijkstra(int z)
		{
			int z2 = z;
			alg();

			String s = new String();
			int n = graf.getNrVarfuri();
			for(int i=0;i<n;i++)
				System.out.println("d=" + d[i]);
			s = String.valueOf(z);
			while(p[z] != 0)
			{
				s = s+" "+ String.valueOf(p[z]);
				z = p[z];
			}
			s = s + " " + '0';
			
			String s2 = new String();
			for(int i=s.length()-1;i>=0;i--)
				s2 = s2+s.charAt(i);
			
			return s2+"\n Costul total este "+d[z2];
		}
	
}
